package easy.AverageOfLevelsBinaryTree;


import java.util.ArrayList;
import java.util.List;

public class AverageOfLevelsInBinaryTree {
    public List<Double> averageOfLevels(TreeNode root) {
        List nodeList = new ArrayList<TreeNode>();
        List sumList = new ArrayList<Double>();
        nodeList.add(root);
        while(!nodeList.isEmpty()){
            double num = 0;
            double sum = 0;
            List nextNodeList = new ArrayList<TreeNode>();
            for(int i=0;i<nodeList.size();i++){
                TreeNode tempNode = (TreeNode) nodeList.get(i);
                sum+=tempNode.val;
                num++;
                TreeNode leftNode = tempNode.left;
                TreeNode rightNode = tempNode.right;
                if(leftNode!=null){
                    nextNodeList.add(leftNode);
                }
                if(rightNode!=null){
                    nextNodeList.add(rightNode);
                }
            }
            nodeList = nextNodeList;
            sumList.add(sum/num);
        }
        return sumList;
    }
}
